package com.zcmyth;

/*
Given an array A of n elements and an integer k (where k<n). 
Elements {A[0]...A[k]}and {A[k+1]...A[n]} are already sorted. Give an algorithm to sort 
the array A in O(n) time and O(1)space
*/
public class MergeArray
{
	public static void main(String[] args) {
		MergeArray m = new MergeArray();
		m.mix2Array();
	}

	int[] arr = {1,2,5,7,9,0,4,6,8,10};

	public boolean mix2Array()
	{

		if (arr == null || arr.length % 2 != 0)
		{
			return false;
		}

		for (int i = 0; i < arr.length - 2; i++)
		{
			int targetIndex = target(i, arr.length);
			while (targetIndex < i)
			{
				targetIndex = target(targetIndex, arr.length);
			}
			if (i != targetIndex)
			{
				swap(i, targetIndex);
			}
			printArray();
		}
		
		return true;
	}

	private void printArray()
	{
		for(int i : arr)
		{
			System.out.print(i+" ");
		}
		System.out.println();
	}
	private void swap(int i, int targetIndex)
	{
		arr[i] ^= arr[targetIndex];
		arr[targetIndex] ^= arr[i];
		arr[i] ^= arr[targetIndex];
	}

	private int target(int i, int length)
	{
		if (i % 2 == 1)
		{
			return length / 2 + i / 2;
		}
		else
		{
			return i / 2;
		}
	}
}